package vip.zhenzicheng.algorithm.leetcode.str;

/**
 * <a href="https://leetcode.cn/problems/implement-trie-prefix-tree/">实现 Trie（前缀树） [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-30 17:36
 */
public class ImplementTriePrefixTree_208 {

  class Trie {

    /*前缀树根节点*/
    TrieNode root;

    public Trie() {
      root = new TrieNode();
    }

    public void insert(String word) {
      insertChar(word, 0, root);
    }

    public boolean search(String word) {
      return searchChar(false, word, 0, root);
    }

    public boolean startsWith(String prefix) {
      return searchChar(true, prefix, 0, root);
    }

    /*用递归实现插入字符串*/
    void insertChar(String word, int index, TrieNode curNode) {
      if (index == word.length()) {
        curNode.isEnd = true;
        return;
      }

      // 计算字符在数组中的下标
      int charIndex = word.charAt(index) - 'a'; // 使用[0, 25] 表示 ['a', 'z']上的前缀节点，因为一共有26个小写字母一一对应
      if (curNode.children[charIndex] == null) {
        curNode.children[charIndex] = new TrieNode();
      }
      // 递归查找下一个字符，但是当前节点变为刚刚出现字符所在层的那一个节点
      insertChar(word, index + 1, curNode.children[charIndex]);
    }


    boolean searchChar(boolean isPrefix, String word, int index, TrieNode curNode) {
      if (index == word.length()) { // 找完时判断
        return isPrefix || curNode.isEnd;
      }
      int charIndex = word.charAt(index) - 'a'; // 找到这一层对应前缀节点位置
      if (curNode.children[charIndex] == null) {
        return false;
      }
      return searchChar(isPrefix, word, index + 1, curNode.children[charIndex]);
    }
  }

  class TrieNode {

    // 所有可能出现的子节点26种
    TrieNode[] children;
    boolean isEnd;

    TrieNode() {
      // 输入仅含小写字母所以是26个节点，最终一个完整的trie数元素个数为 root + 26 * 26个
      children = new TrieNode[26];
      isEnd = false;
    }
  }

  /*
   * Your Trie object will be instantiated and called as such:
   * Trie obj = new Trie();
   * obj.insert(word);
   * boolean param_2 = obj.search(word);
   * boolean param_3 = obj.startsWith(prefix);
   */
}
